The invention pertains to methods and apparatus for performing multiplication in the Galois field, and encoders and decoders that use such methods and apparatus.
Arithmetic operations in the Galois field GF(2m) have numerous applications in coding theory, computer algebra, communications systems, and cryptography. Most of these applications require fast methods or simple, inexpensive integrated circuits for performing arithmetic operations such as addition, multiplication, squaring, and exponentiation. The relative speed of a method is referred to herein as an method""s time-complexity; the relative circuit area (typically semiconductor wafer area) required to implement the method in an integrated circuit is referred to as a method""s area-complexity.
The Galois field GF(2m) is a set containing a finite number (2m)of elements, wherein m is a positive integer. The elements of the Galois field GF(2m) can be represented in many ways and a representation is said to be isomorphic with respect to another representation if the two representations have the same number of elements and the properties of the elements are the same, but the elements occur in a different order. Even if two representations are isomorphic, the time- and area-complexity of arithmetic operations can differ.
Prior-art methods for multiplication in GF(2m) include the Massey-Omura method disclosed in U.S. Pat. No. 4,587,627. The Massey-Omura method uses a so-called normal basis representation of the elements of GF(2m). Other methods for multiplication using a so-called canonical basis representation have been described in, for example, Mastrovito, xe2x80x9cVLSI Architectures for Multiplication over the Finite Field GF(2m),xe2x80x9d Lecture Notes in Computer Science, vol. 357, pp. 297-309 (1988); Itoh and Tsujii, xe2x80x9cStructure of Parallel Multipliers for a Class of Finite Fields GF(2m),xe2x80x9d Information and Computation, vol. 83, pp. 21-40, 1989; and Koxc3xa7 and Sunar, xe2x80x9cLow-Complexity Bit-Parallel Canonical and Normal Basis Multipliers for a Class of Finite Fields,xe2x80x9d IEEE Trans. on Computers, vol. 47, pp. 353-356, March, 1998. These canonical basis methods are generally considered superior to the Massey-Omura method because of their superior time-complexity or area-complexity. Efficient methods using the normal basis for special classes of Galois fields have been disclosed by, e.g., Hasan et al., xe2x80x9cA Modified Massey-Omura Parallel Multiplier for a Class of Finite Fields,xe2x80x9d IEEE Trans. on Computers, vol. 42, pp. 1278-1280, October, 1993. Unfortunately, these methods work only for Galois fields having a particular type of basis (a so-called type I optimal normal basis). The Massey-Omura method appears to be the only method useful with optimal normal bases of both type I and type II. Unfortunately, the area-complexity of the Massey-Omura method is about twice that of these more specialized methods. For example, in an integrated circuit implementation, the Massey-Omura method requires 2(m2xe2x88x92m) XOR gates while the more specialized multipliers of Koxc3xa7 and Sunar, and Hasan et al. require only m2xe2x88x921 XOR gates and therefore require less wafer area to implement in an integrated circuit.
Because many practical applications of Galois fields require rapid computations and simple, inexpensive hardware or software, improved methods and apparatus for Galois field arithmetic are needed. For example, digital data blocks of length m can be conveniently treated as elements of the finite Galois field GF(2m) and methods and apparatus for such digital data blocks have many practical applications.
Multi plication methods and apparatus for manipulating digital data blocks represented as elements of the finite Galois field GF(2m) are provided. In a representative method, a product C=Axc2x7B of elements A, B of GF(2m) is obtained by converting the elements A, B from an optimal normal basis representation to a representation in a modified basis N by rearrangement of coefficients ai, bj of A, B, respectively. The elements A, B both correspond to respective digital data blocks, represented in GF(2m). The product C is obtained in the modified basis and can be converted into the optimal normal basis or can be left in the modified basis. For example, if additional multiplications are to be performed, the product C is generally left in the modified basis, whereas if no additional multiplications are needed, the product C can be transformed into the optimal normal basis using a rearrangement of some or all of the coefficients of C. If a representation of the product C in the modified basis is suitable, transformation into the optimal normal basis is omitted.
The elements A, B have respective coefficients axe2x80x2j and bxe2x80x2j in the optimal normal basis, and coefficients aj, bj in the modified basis are obtained using the rearrangement:                     j        =                  {                                                    k                                                                                                        if                      ⁢                                              xe2x80x83                                            ⁢                      1                                        ≤                    k                    ≤                    m                                    ,                                                                                                                          (                                                                  2                        ⁢                        m                                            +                      1                                        )                                    -                  k                                                                                                                        if                      ⁢                                              xe2x80x83                                            ⁢                      m                                        +                    1                                    ≤                  k                  ≤                                      2                    ⁢                                          m                      .                                                                                                                              (        1        )            
where k=2ixe2x88x921 mod (2m+1) and aj=axe2x80x2i and bj=bxe2x80x2i.
Coefficients cl of the product C are obtained by summing products aibj of the coefficients such that:       c    l    =                    ∑                  j          =          1                          m          -          1                    ⁢              (                                            a              j                        ⁢                          b                              j                +                l                                              +                                    a                              j                +                l                                      ⁢                          b              j                                      )              +                  ∑                  j          =          1                          l          -          1                    ⁢                        a          j                ⁢                  b                      l            -            j                                +                  ∑                  j          =          1                l            ⁢                        a                      m            -            l            +            j                          ⁢                  b          m                      -                  j                  m          -          j          +          1                    .      
According to another aspect of the invention, a multiplier is provided for multiplication in GF(2m). A representative embodiment of such a multiplier comprises AND gates for obtaining products of coefficients(such as aibj) and XOR gates for summing the products. The multiplier can include a converter that transforms the coefficients of an element A of GF(2m) expressed in an optimal normal basis to a modified basis. In another embodiment, the multiplier is an integrated circuit.
According to yet another aspect of the invention, a computer-readable medium is provided that includes software for performing multiplication in GF(2m). The software includes a conversion component that converts a representation of an element A, expressed in an optimal normal basis, to a modified basis. The software also includes instructions for calculating a product C=Axc2x7B by calculating products aibj of coefficients of A and B, and summing the products to obtain coefficients of C in the modified basis. In a further embodiment, instructions are provided for transforming the product into an optimal normal or other basis.
These and other embodiments and features of the invention are described with reference to the accompanying drawings.